<?php

class couponOptimalAlgorithm{
    const couponArr = [
        ['id' => 1, 'type' => [1,2,3], 'money' => 80],
        ['id' => 2, 'type' => [3,4], 'money' => 100],
//        ['id' => 3, 'type' => [2,3,4], 'money' => 100],
//        ['id' => 4, 'type' => [1,2,3], 'money' => 100],
//        ['id' => 5, 'type' => [3], 'money' => 100],
//        ['id' => 6, 'type' => [4], 'money' => 100],
//        ['id' => 7, 'type' => [5], 'money' => 100],
    ];
    const goodsArr = [
//        ['id' => 1, 'type' => 1, 'price' => 200],
//        ['id' => 2, 'type' => 2, 'price' => 200],
        ['id' => 3, 'type' => 3, 'price' => 200],
        ['id' => 4, 'type' => 4, 'price' => 200],
        ['id' => 5, 'type' => 5, 'price' => 200],
        ['id' => 6, 'type' => 6, 'price' => 200],
        ['id' => 7, 'type' => 7, 'price' => 200],
    ];

    const typeKey = 'type';
    const couponMoneyKey = 'money';
    const goodsPriceKey = 'price';

    function coupon($couponArr = self::couponArr, $goodsArr = self::goodsArr, $couponNum = null ){

        $couponArr = array_column($couponArr, null, 'id');
        $goodsArr = array_column($goodsArr, null, 'id');
        $keyArr = array_keys($couponArr);
        if($couponNum === null){
            $couponNum = count($keyArr);
        }

        //优惠券排列组合 e.g: ['1,2','1,3','2,3','1,2,3']
        if($couponNum <= 1){
            $arrCouponPlanKey = self::getCombination($keyArr, $couponNum);
        }
        else{
            $arrCouponPlanKey = [];
            for($i= 1; $i<=$couponNum; $i++){
                $temp = self::getCombination($keyArr, $i);
                $arrCouponPlanKey = array_merge($arrCouponPlanKey, $temp);
            }
        }
        $data = [
            'num' => 0,          //商品计数器
            'moneySum' => 0,
            'plan' => [],       //优惠券方案id数组
            'plan_type' => [],  //商品对应分类id数组
            'plan_goods' => [], //优惠券对应所有商品数组
            'all_goods' => [],  //优惠券对应所有商品数组
            'all_coupon' => $couponArr,  //所有优惠券
        ];

        /* 求商品的排列组合 start↓↓↓↓↓  */
        //1: 找到所有符合条件的商品 all_goods
        foreach ($arrCouponPlanKey as $couponKeyPlan){
            $couponKeyPlanArr = explode(',', $couponKeyPlan);   //排列组合的某一个元素, 字符串截取变成数组
            $tempGoodsArr = $goodsArr;
            foreach ($couponKeyPlanArr as $keyC => $couponKey){ //循环组合元素的数组
                foreach ($tempGoodsArr as $keyG => $good){      //循环所有商品
                    $data['plan'][$couponKey] = $couponKey;
                    //判断 商品类型 是否在优惠劵类型中,
                    $data = self::goodsInType($data, $couponArr, $couponKey, $good);
                }

            }
        }

        //2: 根据all_goods 求商品的排列组合
        $goodsIdArr = array_column($data['all_goods'], 'order_goods_id');
        $arrGoodsPlanKey = [];  //符合条件的商品的排列组合
        if(count($goodsIdArr) <= 1){
            $arrGoodsPlanKey = self::getCombination($goodsIdArr, $couponNum);
        }
        else{
            for($i= 1; $i<=count($goodsIdArr) ; $i++){
                $temp = self::getCombination($goodsIdArr, $i);
                $arrGoodsPlanKey = array_merge($arrGoodsPlanKey, $temp);
            }
        }
        //  求商品的排列组合 end ↑↑↑↑↑

        // 商品的排列组合+ 优惠券的排列组合  进行一一匹配 算出所有的优惠方案金额 start  ↓↓↓↓↓
        $jiShuQi = 0;
        $combinationArr = [];
        foreach ($arrCouponPlanKey as $couponKeyPlan){
            $couponKeyPlanArr = explode(',', $couponKeyPlan);
            foreach ($arrGoodsPlanKey as $goodsPlan){
                $goodKeyPlanArr = explode(',', $goodsPlan);

                //如果优惠券数量大于商品数量跳过
                if(count($couponKeyPlanArr) > count($goodKeyPlanArr)){
                    continue;
                }
                $temp = [];
                $temp['coupon'] = $couponKeyPlanArr;
                $temp['good'] = $goodKeyPlanArr;
                $combinationArr[$jiShuQi] = $temp;
                $jiShuQi++;
            }
        }
        $resCombinationCouponAndGood = self::combinationCouponAndGood($combinationArr, $data);
        return $resCombinationCouponAndGood;
pj($resCombinationCouponAndGood);

        // 商品的排列组合+ 优惠券的排列组合  进行一一匹配 算出所有的优惠方案金额 start  ↑↑↑↑↑

//echo 'return';
//pj($data);
//pj($arrGoodsPlanKey, 0);
//pj($data);
        /*
        */





    }

    /**
     * Notes: 算出所有的优惠方案金额, 后期可以增加满减, 折扣等计算方式
     * @param $combinationArr
     * @param $data
     * @return array
     * User: SongX DateTime: 2021/8/26 16:19
     */
    static function combinationCouponAndGood($combinationArr, $data){
        $screenData = self::staticScreen($combinationArr, $data);
        $returnData = $max = [
            'plan' => [],
            'preferentialAmount' => 0,
        ];

        foreach ($screenData as $planItem) {
            $thisMoney = 0;
            $planItemArr = explode(',', $planItem);
            foreach ($planItemArr as $plan){
                $planArr = explode('-', $plan);
                $couponId = $planArr[0];
                $goodId = $planArr[1];

                $goodPrice = $data['all_goods'][$goodId]['goodPrice'];
                $preferentialAmount = $couponMoney= $data['all_coupon'][$couponId][self::couponMoneyKey];
                //商品金额小于优惠券金额的时候, 优惠金额=商品金额
                $goodPrice < $couponMoney && $preferentialAmount = $goodPrice;
                $thisMoney += $preferentialAmount;
            }

            if($returnData['preferentialAmount'] < $thisMoney){
                $returnData['preferentialAmount'] = $thisMoney;
                $returnData['plan'] = $planItem;
            }
        }
/*
        //再轮询一遍,
        foreach ($screenData as $planItem) {
            $thisMoney = 0;
            $planItemArr = explode(',', $planItem);
            foreach ($planItemArr as $plan){
                $planArr = explode('-', $plan);
                $couponId = $planArr[0];
                $goodId = $planArr[1];

                $goodPrice = $data['all_goods'][$goodId]['goodPrice'];
                $preferentialAmount = $couponMoney= $data['all_coupon'][$couponId][self::couponMoneyKey];
                //商品金额小于优惠券金额的时候, 优惠金额=商品金额
                $goodPrice < $couponMoney && $preferentialAmount = $goodPrice;
                $thisMoney += $preferentialAmount;
            }
            if($max['preferentialAmount'] == $thisMoney){
                $returnData['preferentialAmount'] = $thisMoney;
                $returnData['planArr'][] = $returnData['plan'] = $planItem;
            }
        }
*/
        return $returnData;

    }

    // 以下方法不需要再修改,  这里是求所有优惠券+商品的最终组合算法的筛选
    static function staticScreen($combinationArr, $data){
        $returnData = [];
        foreach ($combinationArr as $element){
            $couponKeyArr = $element['coupon'];
            $goodKeyArr = $element['good'];
            $arr = [$couponKeyArr, $goodKeyArr];
            //求笛卡尔乘积算法
            $cartesianProduct = self::cartesian($arr);
            //对笛卡尔乘积进行排列组合
            $zuHeArr = self::getCombination($cartesianProduct, count($couponKeyArr));
            //对笛卡尔乘积排列组合之后, 进行去重筛选
            $zuHeShaiXuan = self::cartesianSongX($zuHeArr);
            foreach ($zuHeShaiXuan as $key => $zuHe){
                $itemArr = explode(',', $zuHe);
                $itemResult = true;
                foreach ($itemArr as $val) {
                    if(!isset($data['plan_goods'][$val])){
                        $itemResult = false;
                        break;
                    }
                }
                if($itemResult && !in_array($zuHe, $returnData)){
                    $returnData[] = $zuHe;
                }
            }
        }
        /*
        [
            "1-3",
            "2-3",
            "2-4",
            "1-3,2-4"
        ]
         */


        return $returnData;
    }

    //笛卡尔乘积算法
    static function cartesian($arr,$str = array()){
        //去除第一个元素
        $first = array_shift($arr);
        //判断是否是第一次执行
        if(count($str) >= 1) {
            foreach ($str as $k => $val) {
                foreach ($first as $key => $value) {
                    //最终实现的格式 1,3,76
                    //可根据具体需求进行变更
                    $str2[] = $val.'-'.$value;
                }
            }
        }else{
            //第一次执行, 把第一个数组拆解
            foreach ($first as $key => $value) {
                //最终实现的格式 1,3,76
                //可根据具体需求进行变更
                $str2[] = $value;
            }
        }
        //递归进行拼接
        if(count($arr) > 0){
            $str2 = self::cartesian($arr,$str2);
        }
        //返回最终笛卡尔积
        return $str2;
    }

    /**
     * Notes: 笛卡尔乘积结果组合之后进行去重筛选
     * @param $cartesianProduct
     * [
    "1-a,1-b,1-c",
    "1-a,1-b,2-a",
    "1-a,1-b,2-b",
    "1-a,1-b,2-b",
     ......
     ]
     * @return array
     * User: SongX DateTime: 2021/8/26 14:58
     */
    static function cartesianSongX($cartesianProduct){
        $returnData = [];
        foreach ($cartesianProduct as $item){
            $tempCouponIdArr = [];
            $tempGoodIdArr = [];
            $itemArr = explode(',', $item);

            $num = 0;
            foreach ($itemArr as $val) {
                $valArr = explode('-', $val);
                $couponId = $valArr[0];
                $goodId = $valArr[1];
                if(in_array($couponId, $tempCouponIdArr)){
                    continue;
                }
                if(in_array($goodId, $tempGoodIdArr)){
                    continue;
                }
                $num++;
                $tempCouponIdArr[] = $couponId;
                $tempGoodIdArr[] = $goodId;
            }
            if($num == count($itemArr)){
                $returnData[] = $item;
            }


        }
        return $returnData;
    }

    /**
     * Notes: 优惠券能够匹配的所有商品
     * @param $data
     * @param $couponArr
     * @param $couponKey
     * @param $good
     * @param $couponKeyPlanArr
     * @return mixed
     * User: SongX DateTime: 2021/8/5 17:20
     */
    static function goodsInType($data, $couponArr, $couponKey, $good){
        $typeKey = self::typeKey;
        $couponMoneyKey = self::couponMoneyKey;
        $goodPriceKey = self::goodsPriceKey;


        $couponRow = $couponArr[$couponKey];    //优惠券
        $couponMoney = $couponRow[$couponMoneyKey]; //优惠券金额

        $key = $couponKey.'-'.$good['id'];
        $arr = [
            'id' => $data['num'],
            'key' => $key ,
            'order_goods_id' => $good['id'],
            'shop_coupon_id' => $couponKey,
            'coupon_price' => 0,
            'platform_top_id' => $good[$typeKey],
            'couponMoney' => $couponMoney,
            'goodPrice' =>  $good[$goodPriceKey],
        ];
        //商品分类符合优惠券分类, 加入all_goods
        if(in_array($good[$typeKey], $couponRow[$typeKey])){
            $data['plan_type'][$good[$typeKey]] = $good[$typeKey];
            //如果优惠券金额 < 商品售价, 优惠金额=优惠券的金额
            //如果优惠券金额 > 商品售价, 优惠金额=商品售价
            $arr['coupon_price'] = $couponMoney > $good[$goodPriceKey] ? $good[$goodPriceKey] : $couponMoney;
            $data['plan_goods'][$key] = $arr;


            $data['all_goods'][$good['id']] = $arr;
            $data['num']++;
        }
        return $data;
    }

    /**
     * Notes: 排列组合
     * @param array $sort 组合元素
     * @param int   $num  选几个元素进行组合
     * @return array
     * User: SongX DateTime: 2021/7/28 11:12
     */
    static function getCombination($sort, $num){
        if(count($sort) <= $num && $num > 1){
            $temp = '';
            foreach ($sort as $row) {
                $temp .= $row . ',';
            }
            $temp = substr($temp, 0, -1);
            return [$temp];
        }
        return self::getCombinationBase($sort, $num);
    }
    static function getCombinationBase($sort, $num){
        $result = $data = array();
        if ($num == 1 || $num == 0) {
            return $sort;
        }
        foreach ($sort as $k => $v) {
            unset($sort[$k]);
            $data = self::getCombinationBase($sort, $num - 1);
            foreach ($data as $row) {
                $result[] = $v . ',' . $row;
            }
        }
        return $result;
    }


    //下面3个方法是错误思路, 先保留
    //下面3个方法是错误思路, 先保留
    //下面3个方法是错误思路, 先保留
    /**
     * Notes: 每个分类最大优惠金额
     * @param $couponKeyPlanArr
     * @param $couponArr
     * @return array
     * User: SongX DateTime: 2021/8/4 20:32
     */
    static function maxTypeMoney($couponKeyPlanArr, $couponArr){
        $typeKey = self::typeKey;
        $couponMoneyKey = self::couponMoneyKey;
        $maxTypeMoney = [];  //每个类型对应的最大优惠券金额
        foreach ($couponKeyPlanArr as $keyC => $couponKey){
            $couponRow = $couponArr[$couponKey];    //优惠券
            $couponMoney = $couponRow[$couponMoneyKey]; //优惠券金额
            foreach ($couponRow[$typeKey] as $cType){
                !isset($maxTypeMoney[$cType]) && $maxTypeMoney[$cType] = $couponMoney;
                if($maxTypeMoney[$cType] < $couponMoney){
                    $maxTypeMoney[$cType] = $couponMoney;
                }
            }
        }
        return $maxTypeMoney;
    }
    /**
     * Notes: 返回对应商品组合的 对应优惠券+优惠金额
     * @param array $arrGoodsPlanKey  所有符合商品的 排列组合数组
     * @param array $group            每个商品对应符合的优惠券
     * @return array
     * User: SongX DateTime: 2021/8/5 17:34
     */
    static function computerGoodsBestCoupon($arrGoodsPlanKey, $arrCouponPlanKey, $group){
//pj($arrGoodsPlanKey);
        $dataAllPlan = [];
        foreach ($arrGoodsPlanKey as $goodsPlan){
//pj($goodsPlan);
            $groupTemp = $group;
            $goodsPlanArr = explode(',', $goodsPlan);
//        pj('goods-plan--'.$goodsPlan, 0);
            $thisPlanSumMoney = 0;  //当前计划总金额

            $useCouponType = [];
            pj($group);
            foreach ($arrCouponPlanKey as $couponKeyPlan){
                $couponKeyPlanArr = explode(',', $couponKeyPlan);
                foreach ($couponKeyPlanArr as $couponId){

                }
            }
//            foreach ($goodsPlanArr as $gid){
//                $thisGoodsMoney = 0;    //当前商品最大金额
//
//                foreach ($group[$gid] as $row){
//                    if($row['couponMoney'] > $thisGoodsMoney && !in_array($row['shop_coupon_id'], $useCouponType)){
////            echo '@@@@@@@@@@@@@@@'.$row['shop_coupon_id'].'###';
//                        $thisGoodsMoney = $row['couponMoney'];
//                        $useCouponType[$gid] = $row['shop_coupon_id'];
//                    }
////                    pj($useCouponType, 0);
//                }
//
//                $thisPlanSumMoney += $thisGoodsMoney;
//            }
////            pj("----------", 0);
//            //所有计划总金额
//            $dataAllPlan[$goodsPlan] =  $thisPlanSumMoney;
        }
        arsort($dataAllPlan);
        return $dataAllPlan;

//        $dataData = [];
//        foreach ($dataAllPlan  as $key => $v){
//            $dataData[$v]['goodsPlanSumMoney'] = $v;
//            $dataData[$v]['goodsPlan'][] = $key;
//        }
//
//        return $dataData;
    }
    /**
     * Notes: 根据组合方案的key数组, 返回优惠金额列表
     * @param $couponKeyPlanArr array 优惠券方案列表
     * @param $couponArr        array 优惠券列表
     * @param $goodsArr         array 商品列表
     * @param $couponNum        int   优惠券数量
     * User: SongX DateTime: 2021/7/28 11:23
     */
    static function returnDiscountMoney($couponKeyPlanArr, $couponArr, $goodsArr, $arrCouponPlanKey, $couponNum = 2){
        $typeKey = self::typeKey;
        $couponMoneyKey = self::couponMoneyKey;
        $goodPriceKey = 'price';
        $data = [
            'num' => 0,          //商品计数器
            'moneySum' => 0,
            'plan' => [],       //优惠券方案id数组
            'plan_type' => [],  //商品对应分类id数组
            'plan_goods' => [], //优惠券对应所有商品数组
        ];
        $tempGoodsArr = $goodsArr;
        foreach ($couponKeyPlanArr as $keyC => $couponKey){
//            ['id' => 1, 'type' => [1,2,3], 'money' => 80],
//            ['id' => 5, 'type' => [3], 'money' => 100],
            foreach ($tempGoodsArr as $keyG => $good){
//echo "##{$data['num']}##";
                $data['plan'][$couponKey] = $couponKey;
                //可以使用优惠券的情况
                //1: 商品类型在优惠劵类型中,
                $data = self::goodsInType($data, $couponArr, $couponKey, $good, $couponKeyPlanArr);
            }

        }
//pj($data);
        $group = array_group_by($data['plan_goods'], 'order_goods_id');
        $keyArr = array_keys($group);
//pj($keyArr);
        //所有符合优惠券条件的商品组合  $arrGoodsPlanKey
        if(count($keyArr) <= 1){
            $arrGoodsPlanKey = self::getCombination($keyArr, $couponNum);
        }
        else{
            $arrGoodsPlanKey = [];
            for($i= 1; $i<=count($keyArr) ; $i++){
                $temp = self::getCombination($keyArr, $i);
                $arrGoodsPlanKey = array_merge($arrGoodsPlanKey, $temp);
            }

        }
//pj($arrGoodsPlanKey);
//pj($group);
//echo 'computerGoodsBestCoupon';
        $res = self::computerGoodsBestCoupon($arrGoodsPlanKey, $arrCouponPlanKey, $group);
        pj($res);
//        $goodsPlan = array_key_first($res);
        $goodsPlan = key($res);
        $data['goodsPlan'] = explode(',', $goodsPlan);
        $data['thisGoodsPlanMoney'] = $res[$goodsPlan];

        pj($goodsPlan.'---'.$res[$goodsPlan]);
        pj($data);


//        $data['tempUseType'] = array_values(array_unique($data['tempUseType']));
//
//        $goodsIdArr = array_column($data['plan_goods'], null, 'order_goods_id');
//        $keyArr = array_keys($goodsIdArr);
//        $arrGoodsPlanKey = self::getCombination($keyArr, $couponNum);
//pj($arrGoodsPlanKey, 0);
//        foreach ($arrGoodsPlanKey as $keyGG){
//            $couponKeyPlanArr = explode(',', $couponKeyPlan);
//            $good = $goodsArr[$keyGG];
//            foreach ($couponKeyPlanArr as $keyCC => $couponKey){
//                $couponRow = $couponArr[$couponKey];    //优惠券
//                $couponMoney = $couponRow[$couponMoneyKey]; //优惠券金额
//
//                if($couponMoney){
//
//                }
//            }
//        }

        return $data;
    }
}


$couponArr = [
    ['id' => 1, 'type' => [1,2,3], 'money' => 80],
    ['id' => 2, 'type' => [3,4], 'money' => 100],
    ['id' => 3, 'type' => [2,3,4], 'money' => 100],
    ['id' => 4, 'type' => [1,2,3], 'money' => 100],
    ['id' => 5, 'type' => [7], 'money' => 100],
//    ['id' => 6, 'type' => [4], 'money' => 100],
//    ['id' => 7, 'type' => [5], 'money' => 100],
];
$goodsArr = [
    ['id' => 1, 'type' => 1, 'price' => 200],
    ['id' => 2, 'type' => 2, 'price' => 200],
    ['id' => 3, 'type' => 3, 'price' => 200],
    ['id' => 4, 'type' => 4, 'price' => 200],
    ['id' => 5, 'type' => 5, 'price' => 200],
    ['id' => 6, 'type' => 6, 'price' => 200],
    ['id' => 7, 'type' => 7, 'price' => 200],
];

$t1 = microtime(true);
$class = new couponOptimalAlgorithm();
$res = $class->coupon($couponArr, $goodsArr);
$t2 = microtime(true);
$res['str'] =  '耗时'.round($t2-$t1, 5).'秒';

pj($res);


function pj($data, $isExit = 1)
{
    echo "<pre>";
    echo json_encode($data);
    echo "<pre>";
    if($isExit) exit;
}

/**
 * 二维数组根据某个字段进行分组
 * @param $arr
 * @param $key //要分组的字段, 例如 parent_id
 * @param string $col_id //每个元素的key
 * @return array
 * User: 宋星 DateTime: 2020/10/29 10:46
 */
function array_group_by($arr, $key, $col_id = 'id')
{
    $grouped = array();
    foreach ($arr as $value) {
        $grouped[$value[$key]][$value[$col_id]] = $value;
    }
    if (func_num_args() > 2) {
        $args = func_get_args();
        foreach ($grouped as $key => $value) {
            $parms = array_merge($value, array_slice($args, 2, func_num_args()));
            $grouped[$key] = call_user_func_array('array_group_by', $parms);
        }
    }
    return $grouped;
}
